package huawei.exam3;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/5/31
 */
public class HJ43 {
    /**
     * 迷宫地图
     */
    private int[][] maze;
    /**
     * 标记当前位置是否被访问过
     */
    private boolean[][] visited;
    /**
     * 起点坐标
     */
    private int startX,startY;
    /**
     * 终点坐标
     */
    private int endX,endY;
    /**
     * 记录路径
     */
    private Stack<Point> path;

    public HJ43(int [][]maze,int startX,int startY,int endX,int endY) {
        this.maze = maze;
        this.visited = new boolean[maze.length][maze[0].length];
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
        this.path = new Stack<>();
    }

    public void search() {
        dfs(startX,startY);
    }

    private void dfs(int x,int y) {
        // 跑到了界外，结束
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length) {
            return;
        }

        // 如果当前位置是障碍物或者已被访问过 结束
        if (maze[x][y] == 1 || visited[x][y]) {
            return;
        }

        // 入栈当前位置，并标记当前节点已经被访问
        path.push(new Point(x, y));
        visited[x][y] = true;

        //当前位置是终点位置
        if (x == endX && y == endY) {
            printPath();
            return;
        }

        // 上下左右依次递归遍历
        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x ,y + 1);

        // 回溯
        path.pop();
        visited[x][y] = false;
    }

    private void printPath() {
        path.forEach(point -> {
            System.out.println("(" + point.x + "," + point.y + ")");
        });
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        // 地图数组
        int[][] maze = new int[m][n];
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                maze[i][j] = scanner.nextInt();
            }
        }
        HJ43 hj43 = new HJ43(maze, 0, 0, m - 1, n - 1);
        hj43.search();
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
